#include "elf.h"
#include <fcntl.h>
#include <stdio.h>
#include <malloc.h>
#include <string.h>

#ifdef DEBUG_ALL
#define DEBUG_ELFHDR
#define DEBUG_SECTHDR
#define DEBUG_PROGHDR
#define DEBUG_SYMTAB
#define DEBUG_REL
#define DEBUG_SECTION_INFO
#define DEBUG_SYMTAB_INFO
#define DEBUG_VA
#endif

/*
  struct node_section_total_info is the link node for global section information
  struct node_section_file_info is the link node for local section information
  local section link is included in global section link
  they build section information for all files
*/
struct node_section_file_info
{
	int file_num;
	uint32_t start_offset;
	uint32_t size;
	struct node_section_file_info *next;
};

struct node_section_total_info
{
	// information below are read from section header
	char name[32];
	uint32_t type;
	uint32_t flags;
	uint32_t size;
	uint32_t addralign;

	// information below are calculated after first pass
	uint32_t f_offset;
	uint32_t va;

	// the big section which put all similar sections together
	void * section_content;

	// pointers for visit link
	struct node_section_file_info *head;
	struct node_section_file_info *tail;
	struct node_section_file_info *cur;
	struct node_section_total_info *next;
};

/*
  struct node_symtab_info is the link node for global symtab information
  struct entry_symtab is the symtab information for each file
  struct global_symtab is the arranged global symtab (it is not used currently)
  file symtab information is included in global symtab link
  they build symtab information for all files
*/
struct entry_symtab
{
	// the information below are read from symtab except for file_num
	char name[32];
	uint32_t value;
	uint32_t size;
	uint8_t info;
	char sect_name[32];
	int file_num;
};

struct node_symtab_info
{
	int n_entry; // number of enteries for the symtab
	struct entry_symtab *st;
	struct node_symtab_info *next;
};

struct global_symtab
{
	int n_entry;
	int *offset;
	struct entry_symtab *st;
};

/*
  function to read elf header
  input: fd for input file, buffer for struct Elf
  output: if success, return 0; otherwise < 0
*/
int read_elfhdr(int fd, struct Elf *elfhdr)
{
	if (read(fd, elfhdr, sizeof(struct Elf)) != sizeof(struct Elf))
	{
		printf("Error: cannot read elf header\n");
		return -1;
	}
	if(elfhdr->e_magic != ELF_MAGIC)
	{
		printf("Error: invalid elf file\n");
		return -2;
	}
	return 0;
}

/*
  function to read section header
  input: fd for input file, section header offset in the file, number of sections, buffer for struct Secthdr
  output: if success, return 0; otherwise < 0
*/
int read_secthdr(int fd, int shoff, int n_sh, struct Secthdr *secthdr)
{
	int offset = shoff + n_sh * sizeof(struct Secthdr);
	lseek(fd, offset, SEEK_SET);
	if(read(fd, secthdr, sizeof(struct Secthdr)) != sizeof(struct Secthdr))
	{
		printf("Error: cannot read section header\n");
		return -1;
	}
	return 0;
}

/*
  function to read program header
  input: fd for input file, program header offset in the file, number of segments, buffer for struct Proghdr
  output: if success, return 0; otherwise < 0
*/
int read_proghdr(int fd, int phoff, int n_ph, struct Proghdr *proghdr)
{
	int offset = phoff + n_ph * sizeof(struct Proghdr);
	lseek(fd, offset, SEEK_SET);
	if(read(fd, proghdr, sizeof(struct Proghdr)) != sizeof(struct Proghdr))
	{
		printf("Error: cannot read program header\n");
		return -1;
	}
	return 0;
}

/*
  function to read section content
  input: fd for input file, content offset in the file, content size, buffer
  output: if success, return 0; otherwise < 0
*/
int read_section(int fd, int offset, int size, void *binary)
{
	lseek(fd, offset, SEEK_SET);
	if(read(fd, binary, size) != size)
	{
		printf("Error: cannot read section\n");
		return -1;
	}
	return 0;
}

/*
  function to read shstrtab section
  section shstrtab is an impotant section for analysing sections
  input: fd for input file, elf header, buffer
  output: if success, return 0; otherwise < 0
*/
int read_shstrtab(int fd, struct Elf *elfhdr, char **shstrtab)
{
	struct Secthdr secthdr;

	// step 1: read the section header of shstrtab by elf header's information e_shstrndx
	if(read_secthdr(fd, elfhdr->e_shoff, elfhdr->e_shstrndx, &secthdr) < 0)
		return -1;

	// step 2: read section content
	*shstrtab = (char *)malloc(secthdr.sh_size);
	if(read_section(fd, secthdr.sh_offset, secthdr.sh_size, *shstrtab)<0)
	{
		free(*shstrtab);
		return -1;
	}
	return 0;
}

/*
  function to debug elf header
*/
void dump_elfhdr(struct Elf *elfhdr)
{
	int i;
	printf("ELF HEADER information:\n");
	printf("Elf magic: %x\n", elfhdr->e_magic);
	printf("Elf information: ");
	for(i=0; i<12; i++)
		printf("%d", elfhdr->e_elf[i]);
	printf("\n");
	printf("Type: %d\n", elfhdr->e_type);
	printf("Machine: %d\n", elfhdr->e_machine);
	printf("Version: %d\n", elfhdr->e_version);
	printf("Entry point address: %x\n", elfhdr->e_entry);
	printf("Program header offset: %d\n", elfhdr->e_phoff);
	printf("Section header offset: %d\n", elfhdr->e_shoff);
	printf("Flags: %d\n", elfhdr->e_flags);
	printf("Elf header size: %d\n", elfhdr->e_ehsize);
	printf("Program header size: %d\n", elfhdr->e_phentsize);
	printf("Program header num: %d\n", elfhdr->e_phnum);
	printf("Section header size: %d\n", elfhdr->e_shentsize);
	printf("Section header num: %d\n", elfhdr->e_shnum);
	printf("Section header string table index: %d\n", elfhdr->e_shstrndx);
	printf("\n");
}


/*
  function to debug section header
*/
void dump_secthdr(struct Secthdr *secthdr, char *shstrtab)
{
	printf("SECTION HEADER information:\n");
	printf("Section name: %s\n", &shstrtab[secthdr->sh_name]);
	printf("Section type: %d\n", secthdr->sh_type);
	printf("Section flags: %d\n", secthdr->sh_flags);
	printf("Section address: %x\n", secthdr->sh_addr);
	printf("Section offset: %d\n", secthdr->sh_offset);
	printf("Section size: %d\n", secthdr->sh_size);
	printf("Section link: %d\n", secthdr->sh_link);
	printf("Section information: %d\n", secthdr->sh_info);
	printf("Section address alignment: %d\n", secthdr->sh_addralign);
	printf("Section entry size: %d\n", secthdr->sh_entsize);
	printf("\n");
}

/*
  function to debug program header
*/
void dump_proghdr(struct Proghdr *proghdr)
{
	printf("PROGRAM HEADER information:\n");
	printf("Segment type: %d\n", proghdr->p_type);
	printf("Segment offset: %d\n", proghdr->p_offset);
	printf("Segment va: %x\n", proghdr->p_va);
	printf("Segment pa: %x\n", proghdr->p_pa);
	printf("Segment file size: %d\n", proghdr->p_filesz);
	printf("Segment memory size: %d\n", proghdr->p_memsz);
	printf("Segment flags: %d\n", proghdr->p_flags);
	printf("Segment alignment: %d\n", proghdr->p_align);
	printf("\n");
}

/*
  function to debug symtab section
*/
void dump_symtab(struct Symtab *symtab, int n)
{
	int i;
	printf("SYMTAB information:\n");
	for(i = 0; i < n; i++)
	{
		printf("Symble name: %d; ", symtab[i].st_name);
		printf("Symble value: %x; ", symtab[i].st_value);
		printf("Symble size: %d; ", symtab[i].st_size);
		printf("Symble info: %x; ", symtab[i].st_info);
		printf("Symble other: %d; ", symtab[i].st_other);
		printf("Symble sh index: %x\n", symtab[i].st_shndx);
	}
	printf("\n");
}

/*
  function to debug rel section
*/
void dump_rel(struct Rel *rel, int n)
{
	int i;
	printf("REL information:\n");
	for(i = 0; i < n; i++)
	{
		printf("Rel offset: %d; ", rel[i].r_offset);
		printf("Rel info: %x\n", rel[i].r_info);
	}
	printf("\n");
}

/*
  function to add a section information into the secion information link
  input: section header, shstrtab, file num, link head
*/
void add_section_info(struct Secthdr *sh, char *shstrtab, int file_num, struct node_section_total_info *l_head)
{
	struct node_section_total_info *p = l_head;
	struct node_section_file_info *q;
	uint32_t old_size;

	while(p->next)
	{
		p = p->next;
		if(strcmp(p->name, &shstrtab[sh->sh_name]) == 0) // already have the sction information: add information here
		{
			old_size = p->size;
			p->size += sh->sh_size;
			q = p->tail;
			q->next = (struct node_section_file_info *)malloc(sizeof(struct node_section_file_info));
			q = q->next;
			p->tail = q;
			q->file_num = file_num;
			q->start_offset = old_size;
			q->size = sh->sh_size;
			q->next = NULL;
			return;
		}
	}

	// do not have the section information: add a new node 
	p->next = (struct node_section_total_info *)malloc(sizeof(struct node_section_total_info));
	p = p->next;
	strcpy(p->name, &shstrtab[sh->sh_name]);
	p->type = sh->sh_type;
	p->flags = sh->sh_flags;
	p->size = sh->sh_size;
	p->addralign = sh->sh_addralign;
	p->head = (struct node_section_file_info *)malloc(sizeof(struct node_section_file_info));
	p->tail = p->head;
	p->cur = p->head;
	p->next = NULL;
	q = p->head;
	q->file_num = file_num;
	q->start_offset = 0;
	q->size = sh->sh_size;
	q->next = NULL;
}

/*
  function to debug section information link
*/
void dump_section_info(struct node_section_total_info *l_head)
{
	struct node_section_total_info *p = l_head->next;
	struct node_section_file_info *q;
	printf("Arranged section information:\n");
	printf("\n");
	while(p)
	{
		printf("Section %s:\n", p->name);
		printf("Section type: %d\n", p->type);
		printf("Section flags: %d\n", p->flags);
		printf("Section total size: %d\n", p->size);
		printf("Section address alignment: %d\n", p->addralign);
		printf("\n");
		q = p->head;
		while(q)
		{
			printf("In file %d:\n", q->file_num);
			printf("Section start offset: %d\n", q->start_offset);
			printf("Section size: %d\n", q->size);
			printf("\n");
			q = q->next;
		}
		p = p->next;
	}
}

/*
  function to free section information link
*/
void destroy_section_info(struct node_section_total_info *l_head)
{
	struct node_section_total_info *p = l_head->next, *p1;
	struct node_section_file_info *q, *q1;
	while(p)
	{
		free(p->section_content);
		q = p->head;
		while(q)
		{
			q1 = q->next;
			free(q);
			q = q1;
		}
		p1 = p->next;
		free(p);
		p = p1;
	}
}

/*
  function to add a symtab information into the symtab information link
  input: section link head, entry num, symtab section, strtab section, section header, shstrtab, file num, name list for shstrtab offset
*/
void add_symtab_info(struct node_symtab_info *s_head, int sym_num, struct Symtab *symtab, char *strtab, struct Secthdr *sh, char *shstrtab, int file_num, int *name_list)
{
	int i;
	struct node_symtab_info *p = s_head;

	// add node in the tail of link
	while(p->next)
		p = p->next;
	p->next = (struct node_symtab_info *)malloc(sizeof(struct node_symtab_info));

	// add information
	p = p->next;
	p->n_entry = sym_num;
	p->st = (struct entry_symtab *)malloc(sym_num * sizeof(struct entry_symtab));
	for(i = 0; i < sym_num; i++)
	{
		strcpy(p->st[i].name, &strtab[symtab[i].st_name]);
		p->st[i].value = symtab[i].st_value;
		p->st[i].size = symtab[i].st_size;
		p->st[i].info = symtab[i].st_info;
		if(symtab[i].st_shndx == SHN_ABS)
			strcpy(p->st[i].sect_name, "ABS");
		else if(symtab[i].st_shndx == SHN_COMMON)
			strcpy(p->st[i].sect_name, "COMMON");
		else if(symtab[i].st_shndx == SHN_UNDEF)
			strcpy(p->st[i].sect_name, "UNDEF");
		else
			strcpy(p->st[i].sect_name, &shstrtab[name_list[symtab[i].st_shndx]]);
		p->st[i].file_num = file_num;
	}
	p->next = NULL;
}

/*
  function to debug symtab information link
*/
void dump_symtab_info(struct node_symtab_info *s_head)
{
	int i, n;
	struct node_symtab_info *p;
	p = s_head->next;
	printf("Local symtab information:\n");
	while(p)
	{
		n = p->n_entry;
		for(i = 0; i < n; i++)
		{
			printf("Symble name: %s; ", p->st[i].name);
			printf("Symble value: %x; ", p->st[i].value);
			printf("Symble size: %d; ", p->st[i].size);
			printf("Symble info: %x; ", p->st[i].info);
			printf("Symble section name: %s ", p->st[i].sect_name);
			printf("Symble file num: %d\n", p->st[i].file_num);
		}
		p = p->next;
	}
}

/*
  function to free symtab information link
*/
void destroy_symtab_info(struct node_symtab_info *s_head)
{
	struct node_symtab_info *p, *q;
	p = s_head->next;
	while(p)
	{
		q = p->next;
		free(p->st);
		free(p);
		p = q;
	}
}

/*
  first file pass:
  analyze and manage all the sections of the file
  different sections have different management
  for sections that need to alloc(i.e. .text, .data, .rodata, .bss), we only add the section header information into section information link, as we need to calculate global va afterwards
  for section .symtab and .strtab, we read section content and arrange it into symtab information link
  for other sections, we simply ignore them
*/
int link_pass_1(int fd, struct Elf *eh, char *shstrtab, int file_num, struct node_section_total_info *l_head, struct node_symtab_info *s_head)
{
	int i, sym_num;
	struct Secthdr sh;
	struct Symtab *symtab;
	char *strtab;
	int *name_list;
	name_list = malloc(sizeof(int) * eh->e_shnum);

	// analyze all the sections in the file
	for(i = 0; i < eh->e_shnum; i++)
	{
		if(read_secthdr(fd, eh->e_shoff, i, &sh) < 0)
			return -1;

#ifdef DEBUG_SECTHDR
		dump_secthdr(&sh, shstrtab);
#endif
		name_list[i] = sh.sh_name;

		// if the section need alloc(.text, .data, .rodata, .bss), add section information into section information link for va calculation
		if(sh.sh_flags & SHF_A)
		{
			add_section_info(&sh, shstrtab, file_num, l_head);
		}

		// if the section is .symtab, read symtab content
		else if(sh.sh_type == SHT_SYMTAB)
		{
			sym_num = sh.sh_size / sh.sh_entsize;
			symtab = (struct Symtab *)malloc(sh.sh_size);
			if(read_section(fd, sh.sh_offset, sh.sh_size, symtab) < 0)
			{
				free(symtab);
				return -1;
			}
#ifdef DEBUG_SYMTAB
			dump_symtab(symtab, sym_num);
#endif
		}

		// if the section is .strtab, read strtab content
		else if(sh.sh_type == SHT_STRTAB && i != eh->e_shstrndx)
		{
			strtab = (char *)malloc(sh.sh_size);
			if(read_section(fd, sh.sh_offset, sh.sh_size, strtab) < 0)
			{
				free(strtab);
				return -1;
			}
		}
	}

	// add symtab information into symtab information link by analyzing the content of .symtab and .strtab
	add_symtab_info(s_head, sym_num, symtab, strtab, &sh, shstrtab, file_num, name_list);

	free(symtab);
	free(strtab);
	free(name_list);
	return 0;
}

/*
  function to build elf header for the output file
*/
void init_elfhdr(struct Elf *eh, uint32_t entry, uint32_t phoff, uint32_t shoff, uint32_t phnum, uint32_t shnum, uint32_t shstrndx)
{
	eh->e_type = ET_EXEC;
	eh->e_entry = entry;
	eh->e_phoff = phoff;
	eh->e_shoff = shoff;
	eh->e_phentsize = sizeof(struct Proghdr);
	eh->e_phnum = phnum;
	eh->e_shnum = shnum;
	eh->e_shstrndx = shstrndx;
}

/*
  function to build section header for the output file
  we only build following sections into output file:
  1. section 0 is null section
  2. from section 1 there are several sections which need to alloc(.text, .data, .rodata, .bss)
  3. the last section is .shstrtab
  so, wo do not build .symtab and .strtab into output file
*/
int init_secthdr(struct node_section_total_info *l_head, struct Secthdr **sh, char **shstrtab, int alloc_offset)
{
	int ret = 2, off_name, i;
	int sz_shstrtab = 2 + strlen(".shstrtab");
	struct node_section_total_info *p;

	// calculate the size of .shstrtab
	p = l_head->next;
	while(p)
	{
		ret++;
		sz_shstrtab += (strlen(p->name) + 1);
		p = p->next;
	}

	// alloc section header and shstrtab
	(*sh) = (struct Secthdr *)malloc(ret * sizeof(struct Secthdr));
	(*shstrtab) = (char *)malloc(sz_shstrtab);

	// build null section
	(*sh)[0].sh_name = 0;
	(*sh)[0].sh_type = 0;
	(*sh)[0].sh_flags = 0;
	(*sh)[0].sh_addr = 0;
	(*sh)[0].sh_offset = 0;
	(*sh)[0].sh_size = 0;
	(*sh)[0].sh_link = 0;
	(*sh)[0].sh_info = 0;
	(*sh)[0].sh_addralign = 0;
	(*sh)[0].sh_entsize = 0;
	(*shstrtab)[0] = '\0';
	off_name = 1;

	// build alloc section
	p = l_head->next;
	for(i = 1; i < ret - 1; i++)
	{
		(*sh)[i].sh_name = off_name;
		(*sh)[i].sh_type = p->type;
		(*sh)[i].sh_flags = p->flags;
		(*sh)[i].sh_addr = p->va;
		(*sh)[i].sh_offset = p->f_offset;
		(*sh)[i].sh_size = p->size;
		(*sh)[i].sh_link = 0;
		(*sh)[i].sh_info = 0;
		(*sh)[i].sh_addralign = p->addralign;
		(*sh)[i].sh_entsize = 0;
		strcpy(&((*shstrtab)[off_name]), p->name);
		off_name += (strlen(p->name) + 1);
		p = p->next;
	}

	// build .shstrtab
	(*sh)[ret-1].sh_name = off_name;
	(*sh)[ret-1].sh_type = SHT_STRTAB;
	(*sh)[ret-1].sh_flags = 0;
	(*sh)[ret-1].sh_addr = 0;
	(*sh)[ret-1].sh_offset = alloc_offset;
	(*sh)[ret-1].sh_size = sz_shstrtab;
	(*sh)[ret-1].sh_link = 0;
	(*sh)[ret-1].sh_info = 0;
	(*sh)[ret-1].sh_addralign = 1;
	(*sh)[ret-1].sh_entsize = 0;
	strcpy(&((*shstrtab)[off_name]), ".shstrtab");

	return ret;
}

/*
  function to build program header for the output file
  we only build 3 segments into output file:
  1. all readonly sections (.text, .rodata) are built into segment 0, which is readonly and executable
  2. all writable sections (.data, .bss) are built into segment 1, which is writable
  3. segment 2 is GNU_STACK, though I don't know what it used for
*/
void init_proghdr(struct Proghdr *ph)
{
        ph[0].p_type = PT_LOAD;
        ph[1].p_type = PT_LOAD;
        ph[2].p_type = PT_GNU_STACK;
	ph[0].p_offset = 0;
        ph[2].p_offset = 0;
	ph[0].p_va = 0x8048000;
	ph[2].p_va = 0;
	ph[0].p_pa = 0x8048000;
	ph[2].p_pa = 0;
	ph[0].p_filesz = 0;
	ph[1].p_filesz = 0;
	ph[2].p_filesz = 0;
	ph[0].p_memsz = 0;
	ph[1].p_memsz = 0;
	ph[2].p_memsz = 0;
	ph[0].p_flags = PF_R | PF_X;
	ph[1].p_flags = PF_R | PF_W;
	ph[2].p_flags = PF_R | PF_W;
	ph[0].p_align = 0x1000;
	ph[1].p_align = 0x1000;
	ph[2].p_align = 0x4;
}

/*
  function to arrange section information link, calculate va, and put similar sections together
  in this function, we do these 3 things by visiting section information link
*/
int calculate_va(struct node_section_total_info *l_head, struct Proghdr *ph)
{
	struct node_section_total_info *p;
	uint32_t va, bias, file_offset;
	p = l_head->next;
	va = ph[0].p_va;
	file_offset = sizeof(struct Elf);
	int sect_num = 2;
	while(p)
	{
		sect_num++;
		p = p->next;
	}

	// the start of the output file is elf header, program header and section header
	// so the sections are start behind three headers
	// and va MUST add file_offset, though I don't know why
	p = l_head->next;
	file_offset += (3 * sizeof(struct Proghdr) + sect_num * sizeof(struct Secthdr));
	va += file_offset;
	ph[0].p_filesz += file_offset;
	ph[0].p_memsz += file_offset;

	// find sections which is readonly, build them into segment 0
	while(p)
	{
		if(!(p->flags & SHF_W))
		{
			p->section_content = malloc(p->size);
			// manage address allignment
			if(va % p->addralign != 0)
			{
				bias = p->addralign - va % p->addralign;
				va += bias;
				ph[0].p_filesz += bias;
				ph[0].p_memsz += bias;
				file_offset += bias;
			}
			p->f_offset = file_offset;
			p->va = va;
			va += p->size;
			ph[0].p_filesz += p->size;
			ph[0].p_memsz += p->size;
			file_offset += p->size;
		}
		p = p->next;
	}

	// section 1 and section 0 must placed into two different blocks by va, so we must add 0x1000 to va, but file offset will not change
	p = l_head->next;
	va += 0x1000;
	ph[1].p_offset = file_offset;
	ph[1].p_va = va;
	ph[1].p_pa = va;

	// find sections which is writable, build them into segment 1
	// t is used for manage first address allignment
	int t = 0;
	while(p)
	{
		if(p->flags & SHF_W)
		{
			 p->section_content = malloc(p->size);
			// not .bss: need add both p_filesz and p_memsz
			if(p->type != SHT_NOBITS)
			{
				// manage address allignment
				if(va % p->addralign != 0)
				{
					bias = p->addralign - va % p->addralign;
					va += bias;
					ph[1].p_filesz += bias;
					ph[1].p_memsz += bias;
					file_offset += bias;
					if(t == 0)
					{
						ph[1].p_offset += bias;
						ph[1].p_va += bias;
						ph[1].p_pa += bias;
						ph[1].p_filesz -= bias;
						ph[1].p_memsz -= bias;
					}
				}
				p->f_offset = file_offset;
				p->va = va;
				va += p->size;
				ph[1].p_filesz += p->size;
				ph[1].p_memsz += p->size;
				file_offset += p->size;
			}
			// .bss: only add p_memsz
			else
			{
				p->f_offset = file_offset;
				p->va = va;
				va += p->size;
				ph[1].p_memsz += p->size;
			}
			t = 1;
		}
		p = p->next;
	}

	return file_offset;
}

/*
  function to debug va calculation
*/
void dump_va(struct node_section_total_info *l_head)
{
	struct node_section_total_info *p = l_head->next;
	printf("Calculated va:\n");
	while(p)
	{
		printf("Section %s, ", p->name);
		printf("size: %d, ", p->size);
		printf("file offset: %d. ", p->f_offset);
		printf("va: %x\n", p->va);
		p = p->next;
	}
	printf("\n");
}

/*
  function to visit section information link
  in this function, we give section name, then return the global information node of this section in section information link
*/
struct node_section_total_info *walk_l(struct node_section_total_info *l_head, char *section_name)
{
	struct node_section_total_info *p;
	p = l_head->next;
	while(p)
	{
		if(strcmp(p->name, section_name) == 0)
			return p;
		p = p->next;
	}
	printf("Error: invalid section_total_info\n");
	return NULL;
}

/*
  function to visit section information link
  in this function, we give the global section node and file num, then return the local information node in section information link
*/
struct node_section_file_info *walk_lf(struct node_section_total_info *lp, int file_num)
{
	struct node_section_file_info *p;
	p = lp->head;
	while(p)
	{
		if(p->file_num == file_num)
			return p;
		p = p->next;
	}
	printf("Error: invalid section_file_info\n");
	return NULL;
}

/*
  function to visit symtab information link
  in this function, we give file num and symbol num, then return the exact symtab entry
*/
struct entry_symtab *walk_s_num(struct node_symtab_info *s_head, int file_num, int sym_num)
{
	struct node_symtab_info *p;
	p = s_head->next;
	while(p)
	{
		if((p->st)->file_num == file_num)
			return &((p->st)[sym_num]);
		p = p->next;
	}
	printf("Error: invalid symtab_info\n");
	return NULL;
}

/*
  function to visit symtab information link
  in this function, we give symbol name, then return the symtab entry which is the definition of this symbol
*/
struct entry_symtab *walk_s_name(struct node_symtab_info *s_head, char *name)
{
	int i;
	struct node_symtab_info *p;
	p = s_head->next;
	while(p)
	{
		for(i = 0; i < p->n_entry; i++)
		{
			if(strcmp(((p->st)[i]).name, name) == 0 && strcmp(((p->st)[i]).sect_name, "UNDEF") != 0)
			{
				return &((p->st)[i]);
			}
		}
		p = p->next;
	}
	printf("Error: invalid symtab_info\n");
	return NULL;
}

/*
  function to relocate address
*/
int rel_addr(int fd, struct Elf *eh, struct Secthdr *sh, int n_sh, char *shstrtab, int file_num, struct node_section_total_info *l_head, struct node_symtab_info *s_head)
{
	int i, *A, P, S;
	char *s_name = &shstrtab[sh->sh_name + 4];
	int n_rel = sh->sh_size / sh->sh_entsize;
	struct Rel *reltab = (struct Rel *)malloc(sh->sh_size);
	struct node_section_total_info *lp, *lp2;
	struct node_section_file_info *lfp, *lfp2;
	struct entry_symtab *sp;

	// step 1: read rel section
	if(read_section(fd, sh->sh_offset, sh->sh_size, reltab) < 0)
	{
		free(reltab);
		return -1;
	}
#ifdef DEBUG_REL
	dump_rel(reltab, n_rel);
#endif

	// step 2: find the section which need to relocate
	// for example, if the rel section is .rel.text, we must visit .text section in the section information table
	if((lp = walk_l(l_head, s_name)) == NULL)
	{
		free(reltab);
		return -1;
	}
	if((lfp = walk_lf(lp, file_num)) == NULL)
	{
		free(reltab);
		return -1;
	}

	// step 3: for each entry of the rel table, relocate the referred address
	for(i = 0; i < n_rel; i++)
	{
		// A is a pointer pointed to the place where need to relocate
		// so *A is the value of the place where need to relocate
		A = (int *)(lp->section_content + lfp->start_offset + reltab[i].r_offset);

		// P is the va of the place where need to relocate
		P = lp->va + lfp->start_offset + reltab[i].r_offset;

		// S is the va of the symbol of the relocated place
		// so we must first visit the symtab information table, and find the symtab entry of the symbol
		// then we should visit the section information table, to calculate the va of the symbol
		if((sp = walk_s_num(s_head, file_num, reltab[i].r_info >> 8)) == NULL)
		{
			free(reltab);
			return -1;
		}
		if(strcmp(sp->sect_name, "UNDEF") == 0)
		{
			if((sp = walk_s_name(s_head, sp->name)) == NULL)
			{
				free(reltab);
				return -1;
			}
		}
		if((lp2 = walk_l(l_head, sp->sect_name)) == NULL)
		{
			free(reltab);
			return -1;
		}
		if((lfp2 = walk_lf(lp2, sp->file_num)) == NULL)
		{
			free(reltab);
			return -1;
		}
		S = lp2->va + lfp2->start_offset + sp->value;

		// there are two kinds of relocations
		// if the relocation address is a real address, the relocated address is S + *A
		// if the relocation address is a PC, the relocated address is S + *A - P
		if((reltab[i].r_info & 0xFF) == R_386_32)
			(*A) += S;
		else if((reltab[i].r_info & 0xFF) == R_386_PC32)
			(*A) += (S - P);
		else
		{
			printf("Error: undefined rel info\n");
			free(reltab);
			return -1;
		}
	}
	free(reltab);
	return 0;
}

/*
  second file pass:
  put all the pieces of sections together and relocate address
  different sections have different management
  for sections that need to alloc(i.e. .text, .data, .rodata, .bss), we read the section content and put similar sections together
  for rel section, we calculate and relocate the address referred in the section
  for other sections, we simply ignore them
*/
int link_pass_2(int fd, struct Elf *eh, char *shstrtab, int file_num, struct node_section_total_info *l_head, struct node_symtab_info *s_head)
{
	int i;
	struct Secthdr sh;
	struct node_section_total_info *lp;
	struct node_section_file_info *lfp;

	for(i = 0; i < eh->e_shnum; i++)
	{
		if(read_secthdr(fd, eh->e_shoff, i, &sh) < 0)
			return -1;

		// for alloc sections, we get the information from section information link, and read the content to the global content buffer
		if(sh.sh_flags & SHF_A)
		{
			if((lp = walk_l(l_head, &shstrtab[sh.sh_name])) == NULL)
				return -1;
			if((lfp = walk_lf(lp, file_num)) == NULL)
				return -1;
			if(read_section(fd, sh.sh_offset, sh.sh_size, lp->section_content + lfp->start_offset) < 0)
				return -1;
		}

		// for rel sections, we manage the address relocation
		else if(sh.sh_type == SHT_REL)
		{
			if(rel_addr(fd, eh, &sh, i, shstrtab, file_num, l_head, s_head) < 0)
				return -1;
		}
	}
	return 0;
}

/*
  function to find the program entry
  in our linker, the entry must be function nomain()
  so we visit symble information link to find symbol "nomain"
  then we visit section information link to calculate the va of "nomain"
*/
uint32_t find_entry(struct node_section_total_info *l_head, struct node_symtab_info *s_head)
{
	struct entry_symtab *es;
	struct node_section_total_info *si;
	struct node_section_file_info *sfi;
	if((es = walk_s_name(s_head, "nomain")) == NULL)
		return 0;
	if((si = walk_l(l_head, es->sect_name)) == NULL)
		return 0;
	if((sfi = walk_lf(si, es->file_num)) == NULL)
		return 0;
	return si->va + sfi->start_offset + es->value;
}

/*
  the final function to put all pieces together into the output file
  our output file is build in this order:
  elf header, program header, section header, segment 0, segment 1, section .shstrtab
*/
int write_output_file(struct Elf *eh, struct node_section_total_info *l_head, struct Proghdr *ph, struct Secthdr *sh, int sect_num, char *shstrtab)
{
	int fd, i;
	struct node_section_total_info *p;

	if((fd = open("out", O_WRONLY | O_CREAT | O_TRUNC, 0555)) < 0)
	{
		printf("Error: cannot write output file\n");
		return -1;
	}

	// write elf header
	if(write(fd, eh, sizeof(struct Elf)) < 0)
	{
		printf("Error: cannot write output file\n");
		close(fd);
		return -1;
	}

	// write section content
	p = l_head->next;
	while(p)
	{
		lseek(fd, p->f_offset, SEEK_SET);
		if(write(fd, p->section_content, p->size) < 0)
		{
			printf("Error: cannot write output file\n");
			close(fd);
			return -1;
		}
		p = p->next;
	}

	// write program header
	lseek(fd, eh->e_phoff, SEEK_SET);
	for(i = 0; i < 3; i++)
	{
		if(write(fd, &ph[i], sizeof(struct Proghdr)) < 0)
		{
			printf("Error: cannot write output file\n");
			close(fd);
			return -1;
		}
	}

	// write section header
	lseek(fd, eh->e_shoff, SEEK_SET);
	for(i = 0; i < sect_num; i++)
	{
		if(write(fd, &sh[i], sizeof(struct Secthdr)) < 0)
		{
			printf("Error: cannot write output file\n");
			close(fd);
			return -1;
		}
	}

	// write .shstrtab
	lseek(fd, sh[sect_num-1].sh_offset, SEEK_SET);
	if(write(fd, shstrtab, sh[sect_num-1].sh_size) < 0)
	{
		printf("Error: cannot write output file\n");
		close(fd);
		return -1;
	}

	close(fd);
	return 0;
}

/*
  main function of the link procedure
*/
int main(int argc, char** argv)
{
	int fd, k, i, alloc_offset, sect_num;
	char *filename;
	struct Elf eh;
	struct Secthdr *sh;
	struct Proghdr ph[3];
	char *shstrtab;
	struct node_section_total_info l_head;
	struct node_symtab_info s_head;
	l_head.next = NULL;
	s_head.next = NULL;
	uint32_t entry;

	if(argc < 2)
	{
		printf("Please input file name\n");
		return -1;
	}

	// first pass to scan input files
	for(k = 1; k < argc; k++)
	{
		filename = argv[k];

		if ((fd = open(filename, O_RDONLY)) < 0)
		{
			printf("Error: cannot open file %s\n", filename);
			return -1;
		}

		// read elf header
		if(read_elfhdr(fd, &eh) < 0)
		{
			close(fd);
			return -1;
		}

#ifdef DEBUG_ELFHDR
		dump_elfhdr(&eh);
#endif

		//read .shstrtab
		if(read_shstrtab(fd, &eh, &shstrtab) < 0)
		{
			close(fd);
			return -1;
		}

		// manage first pass
		if(link_pass_1(fd, &eh, shstrtab, k, &l_head, &s_head) < 0)
		{
			close(fd);
			free(shstrtab);
			return -1;
		}

		close(fd);
		free(shstrtab);
	}

#ifdef DEBUG_SECTION_INFO
	dump_section_info(&l_head);
#endif
#ifdef DEBUG_SYMTAB_INFO
	dump_symtab_info(&s_head);
#endif

	// build program headers for executable output file
	// and calculate va for all the sections afer first scan
	init_proghdr(ph);
	alloc_offset = calculate_va(&l_head, ph);

#ifdef DEBUG_VA
	dump_va(&l_head);
#endif
#ifdef DEBUG_PROGHDR
	for(i = 0; i < 3; i++)
		dump_proghdr(&ph[i]);
#endif

	// we can build a global symtab here, but we haven't done it yet
//	build_global_symtab(&s_head, &g_st);

	// second pass to scan input files
	for(k = 1; k < argc; k++)
	{
		filename = argv[k];

		if ((fd = open(filename, O_RDONLY)) < 0)
		{
			printf("Error: cannot open file %s\n", filename);
			return -1;
		}

		// read elf header
		if(read_elfhdr(fd, &eh) < 0)
		{
			close(fd);
			return -1;
		}

		// read .shstrtab
		if(read_shstrtab(fd, &eh, &shstrtab) < 0)
		{
			close(fd);
			return -1;
		}

		// manage second pass
		if(link_pass_2(fd, &eh, shstrtab, k, &l_head, &s_head) < 0)
		{
			close(fd);
			free(shstrtab);
			return -1;
		}

		close(fd);
		free(shstrtab);
	}

	// find the entry point of the program
	// and build section headers for executable output file
	if((entry = find_entry(&l_head, &s_head)) == 0)
	{
		destroy_section_info(&l_head);
		destroy_symtab_info(&s_head);
		return -1;
	}
	sect_num = init_secthdr(&l_head, &sh, &shstrtab, alloc_offset);

#ifdef DEBUG_SECTHDR
	for(i = 0; i < sect_num; i++)
		dump_secthdr(&sh[i], shstrtab);
#endif

	// build elf header for executable output file
	init_elfhdr(&eh, entry, sizeof(struct Elf), sizeof(struct Elf) + 3 * sizeof(struct Proghdr), 3, sect_num, sect_num - 1);

#ifdef DEBUG_ELFHDR
	dump_elfhdr(&eh);
#endif

	// put all pieces together into output file
	if(write_output_file(&eh, &l_head, ph, sh, sect_num, shstrtab) < 0)
	{
		free(sh);
		free(shstrtab);
		destroy_section_info(&l_head);
		destroy_symtab_info(&s_head);
		return -1;
	}

	printf("Completed\n");
	free(sh);
	free(shstrtab);
	destroy_section_info(&l_head);
	destroy_symtab_info(&s_head);
	return 0;
}
